시간 복잡도, 공간 복잡도

• 빅오의 본질
• 공간 복잡도

빅오의 본질

• 빅오의 본질이란 데이터가 늘어날 때 알고리즘의 성능이 어떻게 바뀌는지가 중요한 것
• 컴퓨터 과학에서 O(logN)은 사실 O(log2N)을 줄여부르는 말. 편의를 위해 차수 2를 생략한 것
• N을 2로 나눠서 1이 될 때 까지의 단계수가 걸린다는 뜻

공간 복잡도

• 대부분의 원시값(booleans, numbers, undefined, null)은 constant space를 가진다.
• String은 다르다. 문자열은 O(n)공간이 필요하다.
• reference 타입 - 배열, 객체 -> O(n)

var twoSum = function (nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left < right) {
    if (nums[left] + nums[right] === target) {
      return [left, right];
    }

    if (left === right - 1) {
      left++;
      right = nums.length - 1;
    } else {
      right--;
    }
  }
};

• 변수로 설정된 부분은 모두 number형의 변수입니다.
• string을 제외한 원시값의 공간복잡도는 O1을 가지기에 공간 복잡도는 O1입니다.
• 입력값인 nums의 배열의 크기에 상관없이 같은 길이의 배열을 리턴

var twoSum2 = function (nums, target) {
  const storedNumberAndIndex = {};

  nums.forEach((number, index) => (storedNumberAndIndex[number] = index));

  for (let i = 0; i < nums.length; i++) {
    if (storedNumberAndIndex[target - nums[i]] && storedNumberAndIndex[target - nums[i]] !== i) {
      return [storedNumberAndIndex[target - nums[i]], i];
    }
  }
};

• 사용한 공간은 storedNumberAndIndex 객체와 for문 안의 i
• 객체와 배열은 기본적으로 On 공간복잡도를 가지기 때문에 On입니다.
• forEach 메서드로 인해서 storedNumberAndIndex의 객체는 입력된 값의 배열 길이에 비례하여 공간이 커지게 된다.